home *** CD-ROM | disk | FTP | other *** search
/ PC World 2007 December / PCWorld_2007-12_cd.bin / v cisle / htttrack / httrack-3.41-3.exe / {app} / src / htshash.c < prev    next >
C/C++ Source or Header  |  2006-04-30  |  10KB  |  319 lines
  1. /* ------------------------------------------------------------ */
  2. /*
  3. HTTrack Website Copier, Offline Browser for Windows and Unix
  4. Copyright (C) Xavier Roche and other contributors
  5.  
  6. This program is free software; you can redistribute it and/or
  7. modify it under the terms of the GNU General Public License
  8. as published by the Free Software Foundation; either version 2
  9. of the License, or any later version.
  10.  
  11. This program is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with this program; if not, write to the Free Software
  18. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  19.  
  20.  
  21. Important notes:
  22.  
  23. - We hereby ask people using this source NOT to use it in purpose of grabbing
  24. emails addresses, or collecting any other private information on persons.
  25. This would disgrace our work, and spoil the many hours we spent on it.
  26.  
  27.  
  28. Please visit our Website: http://www.httrack.com
  29. */
  30.  
  31.  
  32. /* ------------------------------------------------------------ */
  33. /* File: httrack.c subroutines:                                 */
  34. /*       hash table system (fast index)                         */
  35. /* Author: Xavier Roche                                         */
  36. /* ------------------------------------------------------------ */
  37.  
  38. /* Internal engine bytecode */
  39. #define HTS_INTERNAL_BYTECODE
  40.  
  41. #include "htshash.h"
  42.  
  43. /* specific definitions */
  44. #include "htsbase.h"
  45. #include "htsopt.h"
  46. #include "htsglobal.h"
  47. #include "htsmd5.h"
  48. #include "htscore.h"
  49. /* END specific definitions */
  50.  
  51. /* Specific macros */
  52. #ifndef malloct
  53. #define malloct malloc
  54. #define freet free
  55. #define calloct calloc
  56. #define strcpybuff strcpy
  57. #endif
  58.  
  59. // GESTION DES TABLES DE HACHAGE
  60. // MΘthode α 2 clΘs (adr+fil), 2e cle facultative
  61. // hash[no_enregistrement][pos]->hash est un index dans le tableau gΘnΘral liens
  62. // #define HTS_HASH_SIZE 8191  (premier si possible!)
  63. // type: numero enregistrement - 0 est case insensitive (sav) 1 (adr+fil) 2 (former_adr+former_fil)
  64. // recherche dans la table selon nom1,nom2 et le no d'enregistrement
  65. // retour: position ou -1 si non trouvΘ
  66. int hash_read(hash_struct* hash,char* nom1,char* nom2,int type,int normalized) {
  67.   char BIGSTK normfil_[HTS_URLMAXSIZE*2];
  68.     char catbuff[CATBUFF_SIZE];
  69.   char* normfil;
  70.   char* normadr;
  71.   unsigned int cle;
  72.   int pos; 
  73.   // calculer la clΘ de recherche, non modulΘe
  74.   if (type)
  75.     cle = hash_cle(nom1,nom2);
  76.   else
  77.     cle = hash_cle(convtolower(catbuff,nom1),nom2);         // case insensitive
  78.   // la position se calcule en modulant
  79.   pos = (int) (cle%HTS_HASH_SIZE);
  80.   // entrΘe trouvΘe?
  81.   if (hash->hash[type][pos] >= 0) {             // un ou plusieurs enregistrement(s) avec une telle clΘ existe..
  82.     // tester table de raccourcis (hash)
  83.     // pos est maintenant la position recherchΘe dans liens
  84.     pos = hash->hash[type][pos];
  85.     while (pos>=0) {              // parcourir la chaine
  86.       switch (type) {
  87.       case 0:         // sav
  88.         if (strfield2(nom1,hash->liens[pos]->sav)) {  // case insensitive
  89. #if DEBUG_HASH==2
  90.           printf("hash: found shortcut at %d\n",pos);
  91. #endif
  92.           return pos;
  93.         }
  94.         break;
  95.       case 1:         // adr+fil
  96.         {
  97.           if (!normalized)
  98.             normfil=hash->liens[pos]->fil;
  99.           else
  100.             normfil=fil_normalized(hash->liens[pos]->fil,normfil_);
  101.           if (!normalized)
  102.             normadr = jump_identification(hash->liens[pos]->adr);
  103.           else
  104.             normadr = jump_normalized(hash->liens[pos]->adr);
  105.           if ((strfield2(nom1,normadr)!=0) && (strcmp(nom2,normfil)==0)) {
  106. #if DEBUG_HASH==2
  107.             printf("hash: found shortcut at %d\n",pos);
  108. #endif
  109.             return pos;
  110.           }
  111.         }
  112.         break;
  113.       case 2:         // former_adr+former_fil
  114.         {
  115.           if (hash->liens[pos]->former_adr) {
  116.             if (!normalized)
  117.               normfil=hash->liens[pos]->former_fil;
  118.             else
  119.               normfil=fil_normalized(hash->liens[pos]->former_fil,normfil_);
  120.             if (!normalized)
  121.               normadr = jump_identification(hash->liens[pos]->former_adr);
  122.             else
  123.               normadr = jump_normalized(hash->liens[pos]->former_adr);
  124.             
  125.             if ((strfield2(nom1,normadr)!=0) && (strcmp(nom2,normfil)==0)) {
  126. #if DEBUG_HASH==2
  127.               printf("hash: found shortcut at %d\n",pos);
  128. #endif
  129.               return pos;
  130.             }
  131.           }
  132.         }
  133.         break;
  134.       }
  135.       // calculer prochaine position dans la chaine
  136.       {
  137.         int old=pos;
  138.         pos=hash->liens[pos]->hash_next[type];   // sinon prochain dans la chaine
  139.         if (old==pos)
  140.           pos=-1;         // erreur de bouclage (ne devrait pas arriver)
  141.       }
  142.     }
  143.     
  144.     // Ok va falloir chercher alors..
  145.     /*pos=hash->max_lien;    // commencer α max_lien
  146.     switch (type) {
  147.     case 0:         // sav
  148.       while(pos>=0) {
  149.         if (hash->liens[pos]->hash_sav == cle ) {
  150.           if (strcmp(nom1,hash->liens[pos]->sav)==0) {
  151.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  152. #if DEBUG_HASH==2
  153.             printf("hash: found long search at %d\n",pos);
  154. #endif
  155.             return pos;
  156.           }
  157.         }
  158.         pos--;
  159.       }
  160.       break;
  161.     case 1:         // adr+fil
  162.       while(pos>=0) {
  163.         if (hash->liens[pos]->hash_adrfil == cle ) {
  164.           if ((strcmp(nom1,hash->liens[pos]->adr)==0) && (strcmp(nom2,hash->liens[pos]->fil)==0)) {
  165.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  166. #if DEBUG_HASH==2
  167.             printf("hash: found long search at %d\n",pos);
  168. #endif
  169.             return pos;
  170.           }
  171.         }
  172.         pos--;
  173.       }
  174.       break;
  175.     case 2:         // former_adr+former_fil
  176.       while(pos>=0) {
  177.         if (hash->liens[pos]->hash_fadrfil == cle ) {
  178.           if (hash->liens[pos]->former_adr)
  179.             if ((strcmp(nom1,hash->liens[pos]->former_adr)==0) && (strcmp(nom2,hash->liens[pos]->former_fil)==0)) {
  180.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  181. #if DEBUG_HASH==2
  182.             printf("hash: found long search at %d\n",pos);
  183. #endif
  184.             return pos;
  185.           }
  186.         }
  187.         pos--;
  188.       }
  189.     }*/
  190. #if DEBUG_HASH==1
  191.     printf("hash: not found after test %s%s\n",nom1,nom2);
  192. #endif
  193.     return -1;    // non trouvΘ
  194.   } else {
  195. #if DEBUG_HASH==2
  196.     printf("hash: not found %s%s\n",nom1,nom2);
  197. #endif
  198.     return -1;    // non trouvΘ : clΘ non entrΘe (mΩme une fois)
  199.   }
  200. }
  201.  
  202. // enregistrement lien lpos dans les 3 tables hash1..3
  203. void hash_write(hash_struct* hash,int lpos,int normalized) {
  204.   char BIGSTK normfil_[HTS_URLMAXSIZE*2];
  205.     char catbuff[CATBUFF_SIZE];
  206.   char* normfil;
  207.   unsigned int cle;
  208.   int pos; 
  209.   int* ptr;
  210.   //
  211.   if (hash->liens[lpos]) {                       // on sait jamais..
  212.     hash->max_lien = max(hash->max_lien,lpos);
  213. #if DEBUG_HASH
  214.     hashnumber=hash->max_lien;
  215. #endif
  216.     // ΘlΘment actuel sur -1 (fin de chaine)
  217.     hash->liens[lpos]->hash_next[0]=hash->liens[lpos]->hash_next[1]=hash->liens[lpos]->hash_next[2]=-1;
  218.     //
  219.     cle = hash_cle(convtolower(catbuff,hash->liens[lpos]->sav),"");    // CASE INSENSITIVE
  220.     pos = (int) (cle%HTS_HASH_SIZE);
  221.     ptr = hash_calc_chaine(hash,0,pos);         // calculer adresse chaine
  222.     *ptr = lpos;                   // noter dernier enregistrΘ
  223. #if DEBUG_HASH==3
  224.     printf("[%d",pos);
  225. #endif
  226.     //
  227.     if (!normalized)
  228.       normfil=hash->liens[lpos]->fil;
  229.     else
  230.       normfil=fil_normalized(hash->liens[lpos]->fil,normfil_);
  231.     if (!normalized)
  232.       cle = hash_cle(jump_identification(hash->liens[lpos]->adr),normfil);
  233.     else
  234.       cle = hash_cle(jump_normalized(hash->liens[lpos]->adr),normfil);
  235.     pos = (int) (cle%HTS_HASH_SIZE);
  236.     ptr = hash_calc_chaine(hash,1,pos);         // calculer adresse chaine
  237.     *ptr = lpos;                   // noter dernier enregistrΘ
  238. #if DEBUG_HASH==3
  239.     printf(",%d",pos);
  240. #endif
  241.     //
  242.     if (hash->liens[lpos]->former_adr) {         // former_adr existe?
  243.       if (!normalized)
  244.         normfil=hash->liens[lpos]->former_fil;
  245.       else
  246.         normfil=fil_normalized(hash->liens[lpos]->former_fil,normfil_);
  247.       if (!normalized)
  248.         cle = hash_cle(jump_identification(hash->liens[lpos]->former_adr),normfil);
  249.       else
  250.         cle = hash_cle(jump_normalized(hash->liens[lpos]->former_adr),normfil);
  251.       pos = (int) (cle%HTS_HASH_SIZE);
  252.       ptr = hash_calc_chaine(hash,2,pos);         // calculer adresse chaine
  253.       *ptr = lpos;                   // noter dernier enregistrΘ
  254. #if DEBUG_HASH==3
  255.       printf(",%d",pos);
  256. #endif
  257.     }
  258. #if DEBUG_HASH==3
  259.     printf("] "); fflush(stdout);
  260. #endif
  261.   }
  262. #if DEBUT_HASH
  263.   else {
  264.     printf("* hash_write=0!!\n");
  265.     abortLogFmt("unexpected error in hash_write (pos=%d)" _ pos);
  266.     exit(1);
  267.   }
  268. #endif
  269.   //
  270. }
  271.  
  272. // calcul clΘ
  273. // il n'y a pas de formule de hashage universelle, celle-ci semble acceptable..
  274. unsigned long int hash_cle(char* nom1,char* nom2) {
  275.   /*
  276.   unsigned int sum=0;
  277.   int i=0;
  278.   while(*nom1) {
  279.     sum += 1;
  280.     sum += (unsigned int) *(nom1);
  281.     sum *= (unsigned int) *(nom1++);
  282.     sum += (unsigned int) i;
  283.     i++;
  284.   }
  285.   while(*nom2) {
  286.     sum += 1;
  287.     sum += (unsigned int) *(nom2);
  288.     sum *= (unsigned int) *(nom2++);
  289.     sum += (unsigned int) i;
  290.     i++;
  291.   }
  292.   */
  293.   return md5sum32(nom1)
  294.         +md5sum32(nom2);
  295. }
  296.  
  297. // calcul de la position finale dans la chaine des elements ayant la mΩme clΘ
  298. int* hash_calc_chaine(hash_struct* hash,int type,int pos) {
  299. #if DEBUG_HASH
  300.   int count=0;
  301. #endif
  302.   if (hash->hash[type][pos] == -1)
  303.     return &(hash->hash[type][pos]);    // premier ΘlΘment dans la chaine
  304.   pos=hash->hash[type][pos];
  305.   while(hash->liens[pos]->hash_next[type] != -1) {
  306.     pos = hash->liens[pos]->hash_next[type];
  307. #if DEBUG_HASH
  308.     count++;
  309. #endif
  310.   }
  311. #if DEBUG_HASH
  312.   count++;
  313.   longest_hash[type]=max(longest_hash[type],count);
  314. #endif
  315.   return &(hash->liens[pos]->hash_next[type]);
  316. }
  317. // FIN GESTION DES TABLES DE HACHAGE
  318.  
  319.